package com.my.study.test;

/**
 * @author: yidujun
 * @create: 2021/07/03 14:17
 */
public class PathNumDynamic {

    public static void main(String[] args) {



    }

    /**
     *
     *
     * @param m 行
     * @param n 列
     * @return
     */
    private static int uniquePaths(int m, int n) {
        if (m <= 0 || n <= 0) {
            return 0;
        }

        int[][] dp = new int[m][n];

        // 1.初始化
        for (int i = 0; i < m; i++) {
            // 最左边的列，都只有一种走法，从上往下
            dp[i][0] = 1;
        }
        for (int i = 0; i < n; i++) {
            // 最上面的行，都只有一种走法，从左往右
            dp[0][i] = 1;
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }

        return dp[m-1][n-1];
    }

    /**
     * 找出路径最短和
     *
     * @param arr
     * @return
     */
    private static int uniquePaths(int[][] arr) {
        // 行
        int m = arr.length;
        //列
        int n = arr[0].length;

        int[][] dp = new int[m][n];

        // 1.初始化
        dp[0][0] = arr[0][0];
        // 1.1 初始化最左边的列
        for (int i = 1; i < m; i++) {
            dp[i][0] = dp[i-1][0] + arr[i][0];
        }
        // 1.1 初始化最上边的行
        for (int i = 1; i < n; i++) {
            dp[0][i] = dp[0][i-1] + arr[0][i];
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + arr[i][j];
            }
        }

        return dp[m-1][n-1];
    }

}
